#include<iostream>
#include<assert.h>
#include<deque>
using namespace std;

namespace yangyi
{
    template<class T,class Container =deque<T>>
    class stack
    {
        public:
        void push(const T& x)
        {
            _com.push_back(x);
        }
        void pop()
        {
            _com.pop_back();
        }
        T& top()
        {
            return _com.back();
        }
        const T& top()const
        {
            return _com.back()
        }
        const T& size()const
        {
            return _com.size();
        }
        bool empty()
        {
            return _com.empty();
        }
        private:
        Container _con;
        deque<T> _com;
    };

    template<class T,class Container = deque<T>>
    class queue
    {
        public:
            void push(const T& x)
            {
                _con.push_back(x);
            }
            void pop()
            {
                _con.pop_front();
            }
            const T& front()const
            {
                return _con.front();
            }
            const T& back()const
            {
                return _con.back();
            }
            T& top()
            {
                return _con.front();
            }
            T& back()
            {
                return _con.back();
            }
            bool empty()
            {
                return _con.empty();
            }
            const T& size()const
            {
                return _con.size();
            }
        private:
        Container _com;
        deque<T> _con;
    };
}

namespace yangyi2
{
    template<class T,class Container = deque<T>>
    class stack
    {
        public:
        void push(const T& x)
        {
            _con.push_back(x);
        }
        void pop()
        {
            _con.pop_back();
        }
        T& top()
        {
            return _con.back();
        }
        const T& top()const
        {
            return _con.back();
        }
        bool empty()
        {
            return _con.empty();
        }
        const T& size()const 
        {
            return _con.size();
        }
        private:
        Container _con;
    };

    template<class T,class Container=deque<T>>
    class queue
    {
        public:
        void push(const T& x)
        {
            _con.push_back(x);
        }
        void pop()
        {
            _con.pop_front();
        }
        const T& top()
        {
            return _con.front();
        }
        const T& back()
        {
            return _con.back();
        }
        bool empty()
        {
            return _con.empty();
        }
        const T& size()const
        {
            return _con.size();
        }
        private:
        Container _con;
    };
}